/**
 * @Date        : 2021/11/5
 * @Author      : sunxiangke(sunxiangke@baidu.com)
 * @Description :
 */

package main

import (
	"math/rand"
	"time"
)

type Skiplist struct {
	Level int
	Head *Node
}

type Node struct{
	Val int
	Forward []*Node
}

var (
	MAXLEVEL = 32
	factor float64= 0.5
)

func randLevel()int{
	level:=1
	rand.Seed(time.Now().UnixNano())
	for rand.Float64()<factor && level<MAXLEVEL{
		level++
	}
	return level
}

func Constructor() Skiplist {
	return Skiplist{
		Level: randLevel(),
		Head: &Node{Forward: make([]*Node,MAXLEVEL)},
	}
}


func (this *Skiplist) Search(target int) bool {
	x:=this.Head
	for i:=this.Level-1;i>=0;i--{
		if x.Forward[i]!=nil && target>x.Forward[i].Val{
			x = x.Forward[i]
		}
	}

	x = x.Forward[0]
	if x!=nil && x.Val==target{
		return true
	}

	return false
}


func (this *Skiplist) Add(num int)  {
	x:=this.Head
	prev:=make([]*Node,MAXLEVEL)
	for i:=this.Level-1;i>=0;i--{
		if x.Forward[i]!=nil && num>=x.Forward[i].Val{
			x = x.Forward[i]
		}
		prev[i] = x
	}

	level:=randLevel()
	node:=&Node{Forward:make([]*Node,level),Val:num}
	if level>this.Level{
		for i:=this.Level;i<level;i++{
			prev[i] = this.Head
		}
		this.Level = level
	}

	for i:=level-1;i>=0;i--{
		node.Forward[i] = prev[i].Forward[i]
		prev[i].Forward[i] = node
	}

}


func (this *Skiplist) Erase(num int) bool {
	x:=this.Head
	for i:=this.Level-1;i>=0;i--{
		for x.Forward[i]!=nil{
			if x.Forward[i].Val==num{
				x.Forward[i] = x.Forward[i].Forward[i]
				return true
			}else if x.Forward[i].Val<num{
				x = x.Forward[i]
			}else{
				break
			}
		}
	}

	return false
}


/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */

func main(){
	obj:=Constructor()
	obj.Add(1)
	obj.Add(2)
	obj.Add(3)
	obj.Search(0)
	obj.Add(4)
	obj.Search(1)
}